1. Field of Invention
The present invention relates to the logic implementation of at least recently used (LRU) algorithm and more particularly to the use of a binary code reflecting the sequence of use of a plurality of units wherein units may be eliminated from use and identified by the code, which code retains the ability to reflect the sequence of use of the remaining units.
2. Description of Prior Art
The present invention finds use in data processing systems wherein a finite number of identical units are utilized in a random sequence, and wherein use of the units must be shared. When one of the units must be assigned to a new use, the one least recently used in the prior sequences is identified for assignment to the new use. In particular, the present invention has been incorporated into a data processing system which utilizes a high speed buffer between a main storage device and a central processing unit. The high speed buffer and associated address array are divided into congruent classes. That is, the high speed buffer is divided into a plurality of sections, each provided with a plurality of addressable entries, and wherein sets of data from the main storage device are to be assigned to a related predetermined entry in one of the plurality of sections in the high speed buffer. The section assigned being the least recently used by the data processing system.
A more complete description of a high speed buffer system divided into congruent classes, and which includes a description of the operation of a least recently used algorithm for replacement purposes, can be found in U.S. Pat. No. 3,588,829 entitled "Integrated Memory System With Block Transfer To A Buffer Store" by Boland et al, issued June 28, 1971 and assigned to the assignee of the present invention. This identified patent is herewith incorporated by reference for the necessary understanding of the need for a least recently used (LRU) algorithm in the environment of a high speed buffer divided into congruents classes. The LRU algorithm is implemented by the updating and decoding of chronology bits.
As further background information representing one form of binary logic for implementing a least recently used algorithm, reference is made to an article entitled "Logical Push-Down List" by J. S. Liptay in the IBM Technical Disclosure Bulletin Vol. 10, No. 10, March 1968, page 1541. As indicated previously, there are a number of invalid binary code combinations which can be assumed by the binary bits reflecting the LRU code. One method of detecting such invalid codes is disclosed in an article entitled "Parallel Validity Checking Of Ordering Or Ranking Vectors", by J. L. Craft in the IBM Technical Disclosure Bulletin Vol. 9, No. 2, July 1966, page 169-170.